//题目:
// 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
// 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>

using namespace std;
//代码：
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        //同种字母个数相同，就是同源字母
        //法一（逆天结构）：成就感满满，就是效率不咋滴
        // vector<vector<string>> ret;
        // ret.resize(strs.size());
        // vector<pair<int,unordered_map<char,int>>> v_hash;
        // int i=0;
        // for(const auto& str:strs)
        // {
        //     unordered_map<char,int> hash;
        //     for(const auto& ch:str)
        //         hash[ch]++;
        //     int flag=false;
        //     for(int i=0;i<v_hash.size();i++)
        //     {
        //         if(v_hash[i].second==hash)
        //         {
        //             ret[v_hash[i].first].push_back(str);
        //             flag=true;
        //         }
        //     }
        //     if(flag==false)
        //     {
        //         v_hash.push_back(make_pair(i,hash));
        //         ret[i++].push_back(str);
        //     }
        // }
        // ret.resize(i);
        // return ret;

        //法二（正经解法）：
        //1.将同源字符串分组————排序法
        unordered_map<string,vector<string>> hash;
        for(const auto& str:strs)
        {
            string tmp=str;
            sort(tmp.begin(),tmp.end());
            hash[tmp].push_back(str);
        }
        //2.将分组后的strs放到结果里
        vector<vector<string>> ret;
        for(const auto& pir:hash) ret.push_back(pir.second);
        return ret;
    }
};